package com.example.designpatterns.iterator.advanced;

import com.example.designpatterns.iterator.Iterator;
import java.util.Stack;

/**
 * 后序遍历迭代器
 * 遍历顺序：左子树 -> 右子树 -> 根节点
 * @param <T> 元素类型
 */
public class PostOrderIterator<T extends Comparable<T>> implements Iterator<T> {
    private Stack<TreeCollection.TreeNode<T>> stack;
    private TreeCollection.TreeNode<T> lastVisited;
    
    /**
     * 创建后序遍历迭代器
     * @param treeCollection 二叉树集合
     */
    public PostOrderIterator(TreeCollection<T> treeCollection) {
        this.stack = new Stack<>();
        lastVisited = null;
        
        // 初始化栈，将根节点及所有左节点入栈
        TreeCollection.TreeNode<T> current = treeCollection.getRoot();
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
    }
    
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    @Override
    public T next() {
        if (!hasNext()) {
            return null;
        }
        
        TreeCollection.TreeNode<T> current = stack.peek();
        T result = null;
        
        // 如果右子树为空或已经访问过右子树，弹出当前节点
        if (current.right == null || current.right == lastVisited) {
            result = current.value;
            lastVisited = stack.pop();
        } else {
            // 遍历右子树
            TreeCollection.TreeNode<T> rightNode = current.right;
            while (rightNode != null) {
                stack.push(rightNode);
                rightNode = rightNode.left;
            }
            // 递归调用获取下一个元素
            return next();
        }
        
        return result;
    }
} 